"""
题目：给定一个无权图、起点和终点，使用 DFS 找到并返回从起点到终点的一条路径（若不存在则返回空列表）。
"""


class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    def get_dfs_path(self, start, end):
        """DFS获取起点到终点的一条路径"""
        if start not in self.vertices or end not in self.vertices:
            return []
        if start == end:
            return [start]

        visited = set()
        path = []  # 存储当前路径

        def dfs(current):
            visited.add(current)
            path.append(current)
            # 找到终点，返回True
            if current == end:
                return True
            # 遍历邻接顶点
            for neighbor in self.vertices[current]:
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
            # 回溯：当前顶点无法到达终点，从路径中移除
            path.pop()
            return False

        dfs(start)
        return path


# 测试
if __name__ == "__main__":
    dir_graph = Graph(is_directed=True)
    dir_graph.add_edge('A', 'B')
    dir_graph.add_edge('B', 'C')
    dir_graph.add_edge('A', 'D')
    dir_graph.add_edge('D', 'C')
    dir_graph.add_edge('C', 'E')

    # 起点A到终点E的路径（可能为[A,B,C,E]或[A,D,C,E]，取决于DFS遍历顺序）
    path = dir_graph.get_dfs_path('A', 'E')
    print("A到E的DFS路径:", path)  # 示例输出: ['A', 'B', 'C', 'E']

    # 不存在的路径（A到F）
    print("A到F的DFS路径:", dir_graph.get_dfs_path('A', 'F'))  # 输出: []